package 中等.动态规划.子序列;

/**
 * 给你一个整数数组 nums 。nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。
 * <p>
 * 返回 nums 中 所有 子数组范围的 和 。
 * <p>
 * 子数组是数组中一个连续 非空 的元素序列。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sum-of-subarray-ranges
 */
public class 子数组范围和_2104 {

    public static void main(String[] args) {

        int[] nums = {4, -2, -3, 4, 1};
        System.out.println(subArrayRanges(nums));

    }

    /**
     * 以i结尾的子数组范围的和是多少
     * dp[i]=dp[i-1]+cur
     * cur的求值：
     * 对于num[0],nums[1]...nums[i]
     * 新加入的子数组有
     * nums[i] nums[i-1]
     * nums[i] nums[i-1] nums[i-2]
     * ...
     * 维护每个子数组的最大最小值
     * 对于新加入的nums[i-2] 只需要判断一个元素
     *
     * @param nums
     * @return
     */
    public static long subArrayRanges(int[] nums) {
        long cur = 0;
        long pre1 = 0;
        for (int i = 1; i < nums.length; i++) {
            cur = 0;
            int max = nums[i];
            int min = nums[i];
            for (int j = i - 1; j >= 0; j--) {
                max = Math.max(max, nums[j]);
                min = Math.min(min, nums[j]);
                cur += max - min;
            }
            cur += pre1;  //需要加上之前的子数组范围和
            pre1 = cur;
        }
        return cur;
    }

}
